package com.linyaonan.leetcode.easy._2389;

import java.util.Arrays;

/**
 * 给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
 *
 * 返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。
 *
 * 子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [4,5,2,1], queries = [3,10,21]
 * 输出：[2,3,4]
 * 解释：queries 对应的 answer 如下：
 * - 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
 * - 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
 * - 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。
 * 示例 2：
 *
 * 输入：nums = [2,3,4,5], queries = [1]
 * 输出：[0]
 * 解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。
 *
 *
 * 提示：
 *
 * n == nums.length
 * m == queries.length
 * 1 <= n, m <= 1000
 * 1 <= nums[i], queries[i] <= 10^6
 *
 * @author: Lin
 * @date: 2024/12/2
 */
public class LongestSubsequenceWithLimitedSum {

    /**
     * 双指针 + 前缀和思路
     * 题目要求最长的子序列，那么按照贪心的思路，数值越小能组成的子序列长度越长
     * 4,5,2,1 排序后 1,2,4,5 前缀和为 1,3,7,12
     * <p>
     * 查找 [3,10,21] 中小于等于 的子序列最长长度 2,3,4
     *
     * @param nums
     * @param queries
     * @return
     */
    public int[] answerQueries(int[] nums, int[] queries) {
        // 1. 首先对nums进行升序排序，组成前缀和
        Arrays.sort(nums);
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            nums[i] = pre;
        }

        for (int i = 0; i < queries.length; i++) {
            queries[i] = check(nums, queries[i]) + 1;
        }

        return queries;
    }

    /**
     * 最右匹配小于等于目标值
     * @param nums
     * @param t
     * @return
     */
    public int check(int[] nums, int t) {
        int l = 0;
        int r = nums.length - 1;
        int tt = -1;
        while (l <= r) {
            int m = (l + r) >>> 1;
            int temp = nums[m];

            if (temp <= t) {
                tt = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return tt;
    }

}

